package fireway;

import java.util.Arrays;

/**
 * 基数排序
 * 2018年 08月 10日 星期五
 *
 * @author fireway
 */
public class RadixSort {
    private static final boolean DEBUG = false;

    private long mLArray[];

    private int mSize;

    private int mMaxDigit;

    private int mBase;

    public static final int BASE_2 = 2;

    public static final int BASE_8 = 8;

    public static final int BASE_10 = 10;

    public static final int BASE_16 = 16;

    public RadixSort(int initialCapacity) {
        mLArray = new long[initialCapacity];
        mSize = 0;
    }

    public RadixSort(long[] array, int size) {
        mLArray = array;
        mSize = size;
    }

    public void insert(long e) {
        mLArray[mSize++] = e;
    }

    public void display() {
        System.out.print("[");
        for (int i = 0; i < mSize; i++) {
            System.out.print(mLArray[i]);
            if (i != mSize - 1) {
                System.out.print(", ");
            }
        }
        System.out.print("]\n");
    }

    /**
     * 基数排序算法实现
     * @param m 最大数有多少位
     */
    public void radixSort() {
        Queue[] tub = new Queue[mBase];
        for (int i = 0; i < mBase; i++) {
            Queue q = new Queue();
            tub[i] = q;
        }

        int power = 1;
        // 进行mMaxDigit次放和收
        for (int i = 0; i < mMaxDigit; i++) {
            if (0 == i) {
                power = 1;
            } else {
                power *= mBase;
            }

            // 将数据元素按关键字第i位的数值放到相应的队列中
            for (int j = 0; j < mSize; j++) {
                int num = (int)((mLArray[j] / power) - mBase * (mLArray[j] / (power * mBase)));
                tub[num].add(mLArray[j]);
            }

            // 顺序回收各队列中的数据元素至数组mLArray中
            int k = 0;
            for (int j = 0; j < mBase; j++) {
                while (!tub[j].isEmpty()) {
                    mLArray[k] = tub[j].remove();
                    k++;
                }
            }

            if (DEBUG) {
                System.out.println("radix sort " + (i + 1) + " : " + Arrays.toString(mLArray));
            }
        }
    }

    public void setMaxDigit(int maxDigit) {
        mMaxDigit = maxDigit;
    }

    public void setBase(int base) {
        mBase = base;
    }
}
